class Solution(object):
    def diffWaysToCompute(self, input):
        """
        :type input: str
        :rtype: List[int]
        """
        acc = ''
        tokens = []
        for c in input:
            if c in ['+', '-', '*']:
                tokens.append(int(acc))
                acc=''
                tokens.append(c)
            else:
                acc+=c
        tokens.append(int(acc))

        ret = []

        length = len(tokens)
        dp = [[[] for _ in range(length)] for _ in range(length)]
        for i in range(length):
            e = tokens[i]
            if isinstance(e, int):
                dp[i][i].append(e)
        for stride in range(2, length, 2):
            for left in range(0, length):
                right = left+stride
                if right>=length: break
                for mid in range(left+1, right, 2):
                    print('left ', left, 'mid ', mid, 'right', right)
                    for lval in dp[left][mid-1]:
                        for rval in dp[mid+1][right]:
                            if tokens[mid]=='+':
                                dp[left][right].append(lval+rval)
                            elif tokens[mid]=='-':
                                dp[left][right].append(lval-rval)
                            else:
                                dp[left][right].append(lval*rval)
        return list(dp[0][-1])

print(Solution().diffWaysToCompute('2*3-4*5'))